1470B - Strange Definition - CodeForces Solution

#include<bits/stdc++.h>
#define whilst while
typedef long long ll;
using namespace std;
int nt[1000006],f[1000006],raw[1000005];
int compress(int x){
	int cur;int pd = 1,dcur;
	while (x > 1){
		cur = nt[x];
		dcur = 0;
		while (nt[x] == cur && x > 1){
			x /= nt[x];
			dcur++;
		}
		if (dcur % 2 == 1) pd *= cur;
	}
	return pd;
}
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);cout.tie(0);
   memset(nt,0,sizeof(nt));
   for (int i = 2 ; i <= 1000000 ; i++)
     if (nt[i] == 0){
       	nt[i] = i;
       	for (int j = i ; j <= 1000000/i ; j++)
    	  if (nt[i*j] == 0) nt[i*j] = i;
    }
   int x,y,t,n,q,m,res1,res2;ll w;
   cin >> t;
   while (t--){
   	cin >> n;m = 0;res1 = 0;res2 = 0;
   	for (int i = 1 ; i <= n ; i++){
   		cin >> x;
   		y = compress(x);
   		if (f[y] > 0) f[y]++;
		 else{
		    f[y] = 1;
			m++;raw[m] = y; 	
		   } 
	   }
	   if (f[1] % 2 == 1) res1 = f[1];
	 for (int i = 1 ; i <= m ; i++){
		res2 = max(res2,f[raw[i]]);
	 	if (f[raw[i]] % 2 == 0) res1 += f[raw[i]];
	 	f[raw[i]] = 0;
	 }   
	 res1 = max(res1,res2);
	 cin >> q;
	 while (q--){
	 	cin >> w;
	 	if (w >= 1) cout << res1;
		 else cout << res2;
		cout << endl; 
	 }   
   } 
   return 0;
}